package com.cn.wxwinnie.arithmetic;

import com.cn.wxwinnie.utils.PrintLine;

/**
 * @author 潇湘暮雨 E-mail:wxwinnie@hotmail.com
 * 
 * @version 创建时间：2014年3月10日 下午10:49:06
 * 
 */
public class StraightInsertionSort {

	public static void main(String[] args) {
		int[] aa = { 69, 45, 12, 52, 22, 65, 34, 37 };
		System.out.println();
		PrintLine.pringLine("排序前");
		System.out.println(aa);// 数组是不能直接打印的
		for (int i = 0; i < aa.length; i++) {
			System.out.print(aa[i] + " ");
		}
		System.out.println();
		PrintLine.pringLine("进入排序");
		aa = straightInsertion(aa);
		PrintLine.pringLine();
		PrintLine.pringLine("直接插入排序后");
		for (int i = 0; i < aa.length; i++) {
			System.out.print(aa[i] + " ");
		}
	}

	/**
	 * 直接插入排序
	 * 
	 * @author 潇湘暮雨 E-mail:wxwinnie@hotmail.com
	 * 
	 * @version 创建时间：2014年3月10日 下午11:08:24
	 * 
	 * @param aa
	 * @return
	 */
	public static int[] straightInsertion(int[] aa) {
		int i, j;
		for (i = 1; i < aa.length; i++) {
			int temp = aa[i];
			for (j = i; j > 0 && aa[j - 1] > temp; j--) {
				aa[j] = aa[j - 1];
				System.out.println();
				for (int k = 0; k < aa.length; k++) {
					System.out.print(aa[k] + " ");
				}
			}
			aa[j] = temp;
			System.out.println();
			for (int k = 0; k < aa.length; k++) {
				System.out.print(aa[k] + " ");
			}System.out.println();
			System.out.println("-------");
		}

		return aa;
	}
	//假设数组为aa[7]
	//从运行的程序来看第一遍的时候先保存下标为1的元素temp = aa[1]，然后比较这个元素与前一个元素aa[0]的大小，如果前一个元素大于这个元素则将这两个元素交换
	//第二遍的时候，先保存下标为2的元素temp=aa[2] ，然后比较下标为2的元素aa[2]和aa[1]，如果两个元素反序，则aa[2]=aa[1],(因为aa[2]已经保存下来了)，
	//然后比较现在的aa[1]与aa[0],如果aa[0]>aa[1]，则aa[1]=aa[0]，然后，aa[0] = temp
	/**
	***********排序前***********
	[I@2f9ee1ac
	69 45 12 52 22 65 34 37 
	***********进入排序***********

	69 69 12 52 22 65 34 37 
	45 69 12 52 22 65 34 37 
	-------

	45 69 69 52 22 65 34 37 
	45 45 69 52 22 65 34 37 
	12 45 69 52 22 65 34 37 
	-------

	12 45 69 69 22 65 34 37 
	12 45 52 69 22 65 34 37 
	-------

	12 45 52 69 69 65 34 37 
	12 45 52 52 69 65 34 37 
	12 45 45 52 69 65 34 37 
	12 22 45 52 69 65 34 37 
	-------

	12 22 45 52 69 69 34 37 
	12 22 45 52 65 69 34 37 
	-------

	12 22 45 52 65 69 69 37 
	12 22 45 52 65 65 69 37 
	12 22 45 52 52 65 69 37 
	12 22 45 45 52 65 69 37 
	12 22 34 45 52 65 69 37 
	-------

	12 22 34 45 52 65 69 69 
	12 22 34 45 52 65 65 69 
	12 22 34 45 52 52 65 69 
	12 22 34 45 45 52 65 69 
	12 22 34 37 45 52 65 69 
	-------

	**************************************
	***********直接插入排序后***********
	12 22 34 37 45 52 65 69 
	**/
}
